package problems.contest;

/**
 * 第 89 场双周赛
 * <p>https://leetcode.cn/contest/biweekly-contest-89</p>
 *
 * @author habitplus
 * @since 22:29, 2022/10/15
 */
public class BCT89 {
    /**
     * T1. 有效时间的数目
     * <p>https://leetcode.cn/problems/number-of-valid-clock-times/</p>
     */
    public int countTime(String time) {
        char[] chs = time.toCharArray();
        int d = 1;

        if (chs[1] != '?') {
            if (chs[0] == '?') d *= chs[1] > '3' ? 2 : 3;
        } else {
            if (chs[0] == '?') d *= 24;
            else d *= chs[0] > '1' ? 4 : 10;
        }

        if (chs[3] == '?') d *= 6;
        if (chs[4] == '?') d *= 10;

        return d;
    }

    /**
     * T2. 二的幂数组中查询范围内的乘积
     * <p>https://leetcode.cn/problems/range-product-queries-of-powers/</p>
     */
    public int[] productQueries(int n, int[][] queries) {
        final int MOD = (int) 1e9 + 7;
        int m = 30; // 2^30
        long[] po = new long[m];
        int sz = 0;
        long p = 1L;
        while (n > 0) {
            if (n % 2 != 0) po[sz++] = p;
            p *= 2;
            n /= 2;
        }

        n = queries.length;
        int[] ret = new int[n];
        for (int i = 0; i < n; ++i) {
            p = 1;
            for (int j = queries[i][0]; j <= queries[i][1]; ++j) {
                p = (p * po[j]) % MOD;
            }
            ret[i] = (int) p;
        }

        return ret;
    }


    /**
     * T3. 最小化数组中的最大值
     * <p>https://leetcode.cn/problems/minimize-maximum-of-array/</p>
     */
    public int minimizeArrayValue(int[] nums) {
        int left = 0, right = 1000000000;

        // 二分答案，寻找最大值
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (check(nums, mid)) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    private boolean check(int[] nums, int k) {
        // 前方的数字还可以帮后方的大数承载多少数字
        long have = 0;
        for (int n : nums) {
            if (n <= k) {
                // 较小数，可以算入承载量
                have += k - n;
            } else {
                // 承载不了了，该答案不可行
                if (have < n - k) return false;
                else have -= (n - k);//减去承载量
            }
        }
        return true;
    }
//    public int minimizeArrayValue(int[] nums) {
//        int n = nums.length;
//
//        int ret = nums[0];
//
//        int sum;
//
//        for (int i = 1; i < n; ++i) {
//            if (nums[i] > nums[i - 1]) {
//                sum = nums[i] + nums[i - 1];
//                nums[i - 1] = sum / 2;
//                nums[i] = sum % 2 == 0 ? sum / 2 : sum / 2 + 1;
//                ret = Math.max(ret, nums[i]);
//            }
//        }
//
//        return ret;
//    }
}
